This invention is related to a method and system for managing data packet queuing in a network gateway environment. More particularly, this invention relates to a method and system that determines both when a packet must be dropped and what packet to drop and which also provides fair queuing link scheduling and hierarchical link sharing.
An important aspect of a data network is management of gateway buffers. For large networks, such as the Internet, a typical gateway buffer will process many data flows, each of which must be buffered in some manner. In practice, the volume of each flow varies and each flow is often xe2x80x9cgreedyxe2x80x9d, seeking to use more of the total buffer space than would be permitted under a fair share allocation. Gateway queuing policies therefore strive to balance maximum throughput with fair allocation of resources.
A common data transmission protocol is Transmission Control Protocol, (xe2x80x9cTCPxe2x80x9d). TCP, the most common data transport layer protocol used on local area networks and the Internet, is an adaptive protocol that seeks to adjust the data transport rate to the available link bandwidth. A TCP connection is a xe2x80x9cclosed loopxe2x80x9d flow whose behavior depends on feedback from the network. This feedback comes in the form of acknowledgments (xe2x80x9cACKsxe2x80x9d) from the destination site corresponding to successfully delivered data packets. When the network is congested, packets are dropped and corresponding ACKs are not returned. When TCP detects that a packet has been dropped, it reduces its data throughput. Thus TCP throughput is sensitive to packet dropping policies at congestion points in the network.
Packet dropping policies drop packets to manage buffer overload conditions and to signal a TCP flow to reduce its data throughput. Conventional packet dropping policies make a determination about one of either (a) when to drop a packet, in which case the packet to be dropped is fixed, or (b) which packet to drop, in which case when to drop is fixed. Conventional policies and can be classified according to which of the decisions are not fixed.
Known packet dropping policies, such as Early Random Drop (xe2x80x9cERDxe2x80x9d), Random Early Detection (xe2x80x9cREDxe2x80x9d), and Flow Random Early Drop (xe2x80x9cFREDxe2x80x9d), determine when a packet drop is required based on the global state of the server or the local states of the individual data flows. Then, once the decision to drop a packet is made, the next incoming packet is dropped. In other words, the xe2x80x9cwhat to dropxe2x80x9d dimension is fixed. Both ERD and RED examine the global state of the server and drop a packet when the occupancy exceeds a given threshold. In ERD, incoming packets are dropped With a predetermined probability when the instantaneous buffer occupancy exceeds a minimum threshold. In RED, packets are always dropped when the global average queue length exceeds a maximum threshold and are dropped with a probability which is a function of the average queue length when the global average queue length is between a minimum threshold value and the maximum threshold. FRED operates similarly to RED, except that the state of each queue is examined. If an arriving packet""s flow queue is greater than a global maximum threshold value, then the packet is dropped. If the queue length is between a minimum and the maximum thresholds, the packed is dropped with a given probability.
A primary drawback to these types of packet drop policies is that the policy is not fair to data flows with input rates that are smaller than their fair output share. This is because all of the data flows experience the same loss rate and, as a result, a flow that uses much less than its fair share still experiences dropped packets. This in turn prevents a low bandwidth adaptive flow, such as TCP, from claiming its fair share of the buffer resources and link bandwidth. In addition, the presence of a non-adaptive flow in the buffer can cause excessive packet drops from all of the flows. If a non-adaptive flow is aggressive in its use of buffer resources, the packet drops will cause the adaptive flows to reduce their bandwidth, thus preventing the adaptive flows from achieving their fair share of resources, even if the congestion is not severe. Furthermore, while FRED addresses some deficiencies of using the global state to make the when-to-drop decision, it may also be unfairly limiting, since no queue is allowed to have a length exceeding the global maximum threshold, even if no other queues are backlogged and thus, excess buffer capacity is available. In addition, neither RED, FRED, nor ERD contemplate managing flows which are assigned different shares of the server""s resources.
Other packet drop algorithms such as Longest Queue Drop (xe2x80x9cLQDxe2x80x9d) and Approximated Longest Queue Drop (ALQD) drop a packet when the buffer is full. Thus, the xe2x80x9cwhen to dropxe2x80x9d dimension for these algorithms is fixed. The xe2x80x9cwhat to dropxe2x80x9d decision is based on the state of the per-flow queues. For example, when the buffer is full, LQD drops a packet from the largest queue. However, algorithms of this type also hinder adaptive flows from reaching their fair share of the link bandwidth. LQD in particular slows down the rate-adjustment of adaptive flows to changes in their allocated fair share due to changing load and the arrival and departure of bursts of competing traffic. LQD also produces large variations in the xe2x80x9cshortxe2x80x9d term throughput of an adaptive flow, reducing the overall throughput.
Accordingly, it would be advantageous to provide a packet drop algorithm which solves these problems, provides an early signaling mechanism for adaptive flows, so that they can adjust their rates before more drastic cuts are needed, and fairly drops packets from flows exceeding a hierarchically assigned share of the server""s resources, thus avoiding consecutive drops from the same flow and causing a xe2x80x9csmoothingxe2x80x9d out of the reductions in the rates of adaptive flows over all of the flows which seek to use more than their respective fair share.
According to the present invention, a method for managing a buffer pool is presented which considers both when a packet should be dropped and which packet should be dropped. The buffer receives data packets from two or more data flows and buffers these packets in a plurality of queues. On a recurring basis, such as the arrival and departure of packets from the buffer, the global average queue occupancy of the queues is determined. A packet-drop indication is provided when the global average exceeds a predetermined maximum threshold. When a packet is to be dropped, each of the queues is then evaluated to locate xe2x80x9coffendingxe2x80x9d queues which are using more than a predetermined amount of the available global queue resources, i.e., those queues which are using more than a determined fair share of the global resources. One of the offender queues is then selected and a packet is dropped from the selected offender queue.
In a preferred embodiment, the global average queue occupancy is determined using an exponential weighted moving average filter. A packet drop indication is also preferably made on a probabilistic basis when the global average queue occupancy exceeds a predetermined minimum threshold but does not exceed the maximum threshold.
The buffer management method of the present invention can be used in combination with any type of link scheduler as part of a network gateway to increase system efficiency. Experimentally, the best performance increase relative to conventional buffer management techniques has been found to occur when early fair drop buffer management is used in connection with a per-flow fair link scheduling algorithm, such as WF, or a hierarchical link scheduling algorithm, such as WF2Q+.